package com.algo.moduleFour;

public class DdaySendBag {
    public int shipWithinDays(int[] weights, int days) {

        int left = 0; int rigth = 0;
        // 设置左右边界
        for(int weight : weights){
            left = Math.max(left,weight);
            rigth += weight;
        }

        // 二分查找
        while(left < rigth){

            int m = (left + rigth) /2;

            if(valid(weights, m, days)){
                rigth = m;
            }else{
                left = m + 1;
            }
        }

        return rigth;


    }

    /**
     * 确认中点是否满足天数要求
     * @param weights
     * @param m
     * @param days
     * @return
     */
    private boolean valid(int[] weights, int m, int days){

        int box = 0;
        int curDay = 1;
        for(int weight : weights){

            if(box + weight > m){
                box =0;
                curDay ++;
            }
            box += weight;
        }

        return curDay <= days;

    }
}
